package demo4;
/*
给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。
 */
public class Test {
    public static void main(String[] args) {

        int[] nums1 = {1,2};
        int[] nums2 = {1,1};
        System.out.println(findMedianSortedArrays(nums1,nums2));
    }


    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        //定义结果，用来保存后返回
        double result = 0;
        //通过两个数组的长度之和，可以知道中位数到底是选择一个，还是两个之间取平均值
        int length_1 = nums1.length;
        int length_2 = nums2.length;
        //偶数代表有两个中间值取平均值，基数代表只有一个中位值
        boolean choose = (length_1+length_2)%2 == 0? true:false;
        //设置一个index来判断，当前的值是否到了我们需要的中位值的地方
        //true:需要取平均值，false:只需要取中间值
        //根据choose来判断给index装两个值还是一个值
        int index = (length_1+length_2-1)/2;

        //分别用i和j表示nums1和nums2的起始下标
        int i = 0;
        int j = 0;
        //定义一个step，用来判断两个数组合并的话，扫描的下标
        int step = 0;
        for(; i < length_1 && j < length_2; step++){
            if(step == index){
                //找到了第一个数
                if(nums1[i] <= nums2[j]){
                    result = nums1[i];
                    i++;
                }else{
                    result = nums2[j];
                    j++;
                }
                //判断是只要一个中位值还是说需要求平均值
                if(choose){
                    //求平均值
                    if(i == length_1){
                        //考虑因为上一个数把其中一个数组抽完了
                        result = (result+(double)nums2[j])/2;
                    }else if(j == length_2){
                        //考虑因为上一个数把其中一个数组抽完了
                        result = (result+(double)nums1[i])/2;
                    }else{
                        //没有抽完数组，所以继续判断左右数组哪个元素大，再进行赋值
                        if(nums1[i] <= nums2[j]){
                            result = (result + (double)nums1[i])/2;
                        }else{
                            result = (result + (double)nums2[j])/2;
                        }
                    }
                }
                //已经找到值了，没有必要再循环，直接返回结果
                return result;
            }

            if(nums1[i] <= nums2[j]){
                //剔除掉小的数
                i++;
            }else{
                j++;
            }

        }
        //整个循环走下来发现有一个数组走完了，但是还没走到目标位置
        //根据计算直接锁定要的中位数在那个没扫描完的数组中的哪个下标中
        if(i == length_1){
            //数组1扫描完了，所以从数组2中找中位值
            result = nums2[j + index - step];//直接找到数组中的这个数，并返回
            if(choose){
                //需要求均值
                result = (result + nums2[j + index - step + 1])/2;
            }
        }else{
            //数组2扫描完了，所以从数组1中找中位值
            result = nums1[i + index - step];//直接找到数组中的这个数，并返回
            if(choose){
                //需要求均值
                result = (result + nums1[i + index - step + 1])/2;
            }
        }
        return result;
    }

}
